/*/*
* File: Iterative Modular Exponentiation
* Author: Dongcheng Li
* Date: 20190918
* Purpose: to solve x^y mod m:
* https://w.ketangpai.com/pages/homework/homework-detail.html
*/
#include<iostream>
using namespace std;
/*
* Input: an integer x,an integer y
* Output: return the result of x^y mod m.
* Purpose: reduce the time to solving x^y mod m.
* Method: According to the known knowledge of mod law.
*/
int mod_exp(int parameter_x, int parameter_y, int parameter_p) 
{//Initial result
	int result = 1;
	while (parameter_y > 0)
	{
		if ((parameter_y & 1) == 1)
		{
			result = (result * parameter_x) % parameter_p;
		}
		parameter_y=parameter_y >> 1;//to see the next bit
		parameter_x = (parameter_x * parameter_x) % parameter_p;
	}
	return result;


}
int main() {
	int integer_A;
	int integer_B;
	int integer_C;
	do {
		cout << "x:" << endl;
		cin >> integer_A;
		cout << "y:" << endl;
		cin >> integer_B;
		cout << "m:" << endl;
		cin >> integer_C;
	} while (integer_A == 0 || integer_B == 0);//Ensure that both integers are not zero.
	cout<<mod_exp(integer_A, integer_B, integer_C);


}